package xyz.scootaloo.oj.offer;

import org.junit.Test;
import xyz.scootaloo.oj.ds.TreeNode;

/**
 * @author flutterdash@qq.com
 * @since 2021/4/12 9:19
 */
public class P68I {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < q.val)
            return dfs(root, p, q);
        else
            return dfs(root, q, p);
    }

    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        // 检查当前节点
        if (root.val >= p.val && root.val <= q.val)
            return root;
        TreeNode res = null;
        // 查找左子树
        if (root.left != null) {
            res = dfs(root.left, p, q);
            if (res != null)
                return res;
        }
        // 检查右子数
        if (root.right != null) {
            res = dfs(root.right, p, q);
        }
        return res;
    }

    @Test
    public void testFunc() {
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node8 = new TreeNode(8);
        TreeNode node0 = new TreeNode(0);
        TreeNode node4 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node9 = new TreeNode(9);
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);

        node6.left = node2;
        node5.right = node8;

        node2.left = node0;
        node2.right = node4;

        node4.left = node3;
        node4.right = node5;

        node8.left = node7;
        node8.right = node9;

        System.out.println(lowestCommonAncestor(node6, node2, node8));
        System.out.println(lowestCommonAncestor(node6, node2, node4));
        System.out.println(lowestCommonAncestor(node6, node0, node5));
    }

}
